/*
实验7-4 是否有回路
分数 25
作者 陈越
单位 浙江大学

如果有向图用邻接表表示，试设计算法判断图中是否存在回路。
函数接口定义：

bool IsAcyclic( LGraph graph );

其中邻接表表示的图 LGraph 的结构定义定义如下：

typedef enum { false, true } bool;
typedef int Vertex;    // 顶点编号类型
typedef char VertInfo; // 顶点信息类型
typedef struct EdgeNode *Position; // 指针即结点位置
struct EdgeNode {
    Vertex dest;     // 边的另一端点编号
    Position next;   // 线性表中下一个元素的位置
};

typedef struct HeadNode *AdjList; // 邻接表

struct HeadNode {
    Position adj;  // 邻接表头指针
    VertInfo data; // 存储顶点信息
};

typedef struct LGraphNode *LGraph; // 邻接表表示的图

struct LGraphNode {
    int n_verts; // 顶点数
    int m_edges; // 边数
    AdjList *ver_list; // 存储顶点邻接表
    bool directed; // true为有向图，false为无向图
};

IsAcyclic 判断 graph 是否无环图，如果是则返回 true，否则返回 false。
裁判定义的测试用主函数通过读入顶点数、边数、以及每条边的两个端点来建立一个图，随后调用
IsAcyclic 进行判断，最后根据判断结果输出 Yes 或 No。

输入样例：

6 9
0 1
0 2
0 3
1 2
2 3
1 4
3 4
3 5
4 5

输出样例：

Yes
*/

#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef int Vertex;                /* 顶点编号类型 */
typedef char VertInfo;             /* 顶点信息类型 */
typedef struct EdgeNode *Position; /* 指针即结点位置 */
struct EdgeNode {
    Vertex dest;   /* 边的另一端点编号 */
    Position next; /* 线性表中下一个元素的位置 */
};
typedef struct HeadNode *AdjList; /* 邻接表 */
struct HeadNode {
    Position adj;  /* 邻接表头指针 */
    VertInfo data; /* 存储顶点信息 */
};
typedef struct LGraphNode *LGraph; /* 邻接表表示的图 */
struct LGraphNode {
    int n_verts;       /* 顶点数 */
    int m_edges;       /* 边数 */
    AdjList *ver_list; /* 存储顶点邻接表 */
    bool directed;     /* true为有向图，false为无向图 */
};

#define kMaxV 1000
/* 裁判实现，细节略 */
void InitGraph(LGraph graph, int kMaxVertex, bool directed);
bool ExistEdge(LGraph graph, Vertex u, Vertex v);
void InsertEdge(LGraph graph, Vertex u, Vertex v);
LGraph BuildGraph();
/* 裁判实现部分结束 */

bool IsAcyclic(LGraph graph);

int main(void) {
    LGraph graph;

    graph = BuildGraph();
    if (IsAcyclic(graph) == true) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }

    return 0;
}
/* 你的代码将被嵌在这里 */

bool DFS(LGraph graph, Vertex v, bool visited[], bool recStack[]) {
    if (!visited[v]) {
        visited[v] = true;
        recStack[v] = true;

        for (Position p = graph->ver_list[v]->adj; p != NULL; p = p->next) {
            if (!visited[p->dest] && DFS(graph, p->dest, visited, recStack)) {
                return true;
            } else if (recStack[p->dest]) {
                return true;
            }
        }
    }
    recStack[v] = false;
    return false;
}

bool IsAcyclic(LGraph graph) {
    bool *visited = (bool *)malloc(graph->n_verts * sizeof(bool));
    bool *recStack = (bool *)malloc(graph->n_verts * sizeof(bool));

    for (int i = 0; i < graph->n_verts; i++) {
        visited[i] = false;
        recStack[i] = false;
    }

    for (int i = 0; i < graph->n_verts; i++) {
        if (DFS(graph, i, visited, recStack)) {
            free(visited);
            free(recStack);
            return false;
        }
    }

    free(visited);
    free(recStack);
    return true;
}